package com.copa.l102;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author copa
 * @createDate 2022-05-19 11:37
 * @function DFS  难得现在自己想出这方法做出来...以前学二叉树的时候都无从下手...
 */
public class Test1 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            // 题目中有可能为空，所以这里处理先返回空
            return result;
        }
        leverIterator(result, root, -1);
        return result;
    }

    /**
     * 遍历
     * @param result 结果集
     * @param root   二叉树
     * @param length 当前树的深度
     */
    private void leverIterator(List<List<Integer>> result, TreeNode root, int length) {
        // 表示每遍历一次就要增加树的深度
        length++;
        if (root == null) {
            // 如果当前遍历的节点没有则返回
            return;
        }
        if (result.size() == length) {
            // 防止结果集报空指针异常
            result.add(new ArrayList<>());
        }
        // 如果当前节点有值则在结果集对应的树的深度加值
        result.get(length).add(root.val);
        // 遍历左子树
        leverIterator(result, root.left, length);
        // 遍历右子树
        leverIterator(result, root.right, length);
    }

    public static void main(String[] args) {
        TreeNode left = new TreeNode(9);
        TreeNode right = new TreeNode(20);
        right.left = new TreeNode(15);
        right.right = new TreeNode(7);
        TreeNode root = new TreeNode(3, left, right);
        List<List<Integer>> result = new Test1().levelOrder(root);
        for (List<Integer> list : result) {
            System.out.println(Arrays.toString(list.toArray()));
        }
    }
}
